The present invention is in the field of data structures for computing devices. More particularly, the present invention relates to methods and arrangements to represent the allocation of integers.
Many processes may require keeping track of the allocation of a set of integers. Each integer in the set may be in use (allocated) or not in use (free). An operating system, for example, may use integers to identify resources, such as lists of DLLs, used by programs running under the operating system. To keep track of the allocation, a process may use a tree structure. A tree consists of nodes and pointers. A node points to its child nodes. The initial node is called the root. To represent an allocation with a tree, the nodes of the tree may contain data structures, each representing the allocation of a subset of the set of integers.
One type of tree is a binary tree. In a binary tree, each node has at most two children, but may have zero or one. A binary tree may be ordered. The nodes of the binary tree may be may be numbered or otherwise labeled so that the left children of a node have a label which is less than the label of the node, and the right children have a label which is greater than the label of the node. One type of ordered binary tree is numbered in preorder: The nodes of a left subtree are numbered, a node is numbered, and the nodes in the right subtree are numbered.
FIG. 1A depicts the representation of the allocation of the integers from 1 to 15 with a binary tree 100 numbered in preorder. For simplicity, in the representation of FIG. 1A, each node represents the state of a single integer and the number of the node coincides with the integer represented by the node; that is, node 8 represents the state of the allocation of integer 8. The label “A” in a node represents an allocated integer, and the label “F” represents a free integer. In the diagram of FIG. 1A, two integers are free, namely 1 and 13. The other integers are allocated. Binary tree 100 contains 15 nodes.